The present invention relates to a system and method for test generation with dynamic constraints, and in particular, to a system and method for dynamically solving constraints by creating a set of instructions which provide a specific, random solution when executed.
Design verification is the process of determining whether an integrated circuit, board, or system-level architecture, exactly implements the requirements defined by the specification of the architecture for that device. Design verification for a device under testing (DUT) may be performed on the actual device, or on a simulation model of the device. For the purposes of explanation only and without intending to be limiting in any way, the following discussion centers upon testing which is performed on simulation models of the device.
As designs for different types of devices and device architectures become more complex, the likelihood of design errors increases. However, design verification also becomes more difficult and time consuming, as the simulation models of the design of the device also become more complex to prepare and to test.
The problem of design verification is compounded by the lack of widely generalizable tools which are useful for the verification and testing of a wide variety of devices and device architectures. Typical background art verification methods have often been restricted to a particular device having a specific design, such that the steps of preparing and implementing such verification methods for the simulation model must be performed for each new device.
The process of verifying a design through a simulation model of the device is aided by the availability of hardware description languages such as Verilog and VHDL. These languages are designed to describe hardware at higher levels of abstraction than gates or transistors. The resultant simulated model of the device can receive input stimuli in the form of test vectors, which are a string of binary digits applied to the input of a circuit. The simulated model then produces results, which are checked against the expected results for the particular design of the device. However, these languages are typically not designed for actual verification. Therefore, the verification engineer must write additional programming code in order to interface with the models described by these hardware description languages in order to perform design verification of the device.
Examples of testing environments include static and dynamic testing environments. A static testing environment drives pre-computed test vectors into the simulation model of the DUT and/or examines the results after operation of the simulation model. In addition, if the static testing environment is used to examine the results which are output from the simulation model, then errors in the test are not detected until after the test is finished. As a result, the internal state of the device at the point of error may not be determinable, requiring the simulation to be operated again in order to determine such internal states. This procedure consumes simulation cycles, and can require the expenditure of considerable time, especially during long tests.
A more useful and efficient type of testing is a dynamic testing environment.
For this type of environment, a set of programming instructions is written to generate the test vectors in concurrence with the simulation of the model of the DUT and while potentially being controlled by the state feedback of the simulated device. This procedure enables directed random generation to be performed and to be sensitive to effects uncovered during the test itself on the state of the simulation model of the device. Thus, dynamic test generation clearly has many advantages for design verification.
Within the area of testing environments, both static and dynamic testing environments can be implemented only with fixed-vector or pre-generation input. However, a more powerful and more sophisticated implementation uses test generation to produce the environment.
One example of such a test generator is disclosed in U.S. patent application Ser. No. 09/020,792, filed on Feb. 6, 1998, incorporated by reference as if fully set forth herein. This test generation procedure interacts with, and sits as a higher level over, such hardware description languages as Verilog and VHDL. The test generation procedure is written in a hardware-oriented verification specific object-oriented programming language. This language is used to write various tests, which are then used to automatically create a device verification test by a test generator module. A wide variety of design environments can be tested and verified with this language. Thus, the disclosed procedure is generalizable, yet is also simple to program and to debug by the engineer.
The disclosed language features a number of elements such as structs for more richly and efficiently describing the design of the device to be simulated by the model. Unfortunately, the disclosed language and resultant test generation environment does not include features for providing a good, random solution for dynamic constraints in a reasonable processing time, and also cannot react dynamically on the same scale as the time period which is actually required for simulation. Furthermore, such features are also not known in the background art, which handles such constraints with a non-random solution.
Therefore, there is an unmet need for, and it would be highly useful to have, a system and method for solving dynamic constraints through a specific, random but correct solution, which would be created by executing a specific set of instructions.
The system and method of the present invention tests the quality of a simulation model for the DUT (device under test) with dynamic constraint solving and test generation for the testing and verification process. The present invention provides such dynamic constraint solving through the creation of a sequence of instructions in a xe2x80x9cgenerator mini-languagexe2x80x9d (GML). These instructions are then executed in order to provide a correct random solution to a given set of dynamic constraints. The process of execution is preferably performed by a constraint resolution engine, optionally and more preferably implemented as software, which manages the requirements imposed by the constraints on the execution, while simultaneously enabling a random solution to the set of constraints to be provided. Such a constraint resolution engine may optionally be viewed as a type of state machine, in which individual elements of the state machine are more preferably represented by one or more dynamic graph(s).
According to the present invention, there is provided a system for dynamically solving constraints for test generation for a DUT (device under test), comprising: (a) a data model for the DUT; (b) an abstract generation machine for solving the constraints by creating a plurality of static instructions; and (c) a test generator for performing test generation according to the plurality of static instructions and according to the data model.
According to another embodiment of the present invention, there is provided a method for dynamically solving a plurality of dynamic constraints for test generation for a DUT (device under test), each constraint featuring at least one parameter, the steps of the method being performed by a data processor, the method comprising the steps of: (a) creating at least one dynamic graph for describing the plurality of dynamic constraints, each node of the at least one dynamic graph representing a constraint or a parameter, and each edge representing a relationship between constraints; (b) reducing a number of nodes for the at least one dynamic graph; and (c) determining a path for traveling through the at least one dynamic graph to create a plurality of instructions for solving the dynamic constraints.
Hereinafter, the term xe2x80x9ccomputing platformxe2x80x9d refers to a particular computer hardware system or to a particular software operating system. Examples of such hardware systems include, but are not limited to, personal computers (PC), Macintosh(trademark) computers, mainframes, minicomputers and workstations. Examples of such software operating systems include, but are not limited to, UNIX, VMS, Linux, MacOS(trademark), DOS, FreeBSD, one of the Windows(trademark) operating systems by Microsoft Inc. (USA), including Windows NT(trademark), Windows95(trademark), Windows98(trademark) and Windows 2000(trademark).
The method of the present invention could also be described as a plurality of instructions being performed by a virtual or actual data processor, such that the method of the present invention could be implemented as hardware, software, firmware or a combination thereof. For the present invention, a software application could be written in substantially any suitable programming language, which could easily be selected by one of ordinary skill in the art. The programming language chosen should be compatible with the computing platform according to which the software application is executed. Examples of suitable programming languages include, but are not limited to, C, C++ and Java.
Hereinafter, the term xe2x80x9cnon-randomxe2x80x9d refers to a process, or an entity selected by the process, which is not random but which is not necessarily deterministic.